//https://leetcode.cn/problems/powx-n/
class Solution {
    public double myPow(double x, long n) {
        double ret = dfs(x, Math.abs(n));
        return (n < 0) ?  1 / ret : ret;
    }
    public double dfs(double x, long n) {
        if(n == 0) return 1;
        double tmp = dfs(x, n / 2);
        return (n % 2) == 0 ? tmp * tmp : tmp * tmp * x;
    }
}